import java.util.ArrayList;

/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class LetterCombinationsOfPhoneNumber {

	static int[] a, b;

	static {
		a = new int[] { 3, 3, 3, 3, 3, 4, 3, 4 };
		b = new int[8];
		for (int i = 1; i < 8; ++i)
			b[i] += b[i - 1] + a[i - 1];
	}

	ArrayList<String> res;
	char[] tmp;

	public void search(String digits, int dep) {
		if (dep == digits.length()) {
			String s = "";
			for (int i = 0; i < dep; ++i)
				s += tmp[i];
			res.add(s);
			return;
		}
		int k = digits.charAt(dep) - '2';
		for (int i = 0; i < a[k]; ++i) {
			tmp[dep] = (char) (b[k] + i + 'a');
			search(digits, dep + 1);
		}
	}

	public ArrayList<String> letterCombinations(String digits) {
		res = new ArrayList<String>();
		tmp = new char[digits.length()];
		search(digits, 0);
		return res;
	}

	public static void main(String[] args) {
		LetterCombinationsOfPhoneNumber a = new LetterCombinationsOfPhoneNumber();
		System.out.println(a.letterCombinations("7"));
	}

}
